#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"../../util/tool.h"
/* 
并非是所有的序列都可以用栈排序法 来进行排序
*/

int maxNumber(int * array,int length){

    int targetIndex = 0;
    for(int index = 1;index < length;++index){

        if(array[targetIndex] < array[index]){

            targetIndex = index;
        }
    }
    return targetIndex;
}

int minNumber(int * array,int length){

    int targetIndex = 0;
    for(int index = 1;index < length;++index){

        if(array[targetIndex] > array[index]){

            targetIndex = index;
        }
    }
    return targetIndex;
}

void checkArrayHelp(int * checkArray,int index,int length){

    int maxIndex = -1;
    int * ptrs = checkArray;
    int tmpLen = length;
    do{
        maxIndex = maxNumber(ptrs,tmpLen);
        if(maxIndex == 0){
            ptrs++;
            // 重新获取maxIndex
            maxIndex = maxNumber(ptrs,tmpLen-1);
        }else if(maxIndex == (tmpLen-1)){
            tmpLen--;
            maxIndex = maxNumber(ptrs,tmpLen);
        }else{

            break;
        }    
    }while(1);
    printf("maxIndex = %d.\n",maxIndex);
    int leftMaxIndex = maxNumber(ptrs,maxIndex);
    int rightMinIndex = minNumber(ptrs + maxIndex + 1,tmpLen-maxIndex);

    printf("left Max Index = %d, right Min Index = %d.\n",leftMaxIndex,rightMinIndex);

    if(*(ptrs+leftMaxIndex) <= *(ptrs+rightMinIndex + maxIndex + 1)){

        printf("take stack sort.\n");
    }else{

        printf("cannot take stack sort.\n");
    }
}

void checkArray(int * checkArray,int number){

    checkArrayHelp(checkArray,0,number);
}


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////// 书上版本 ////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int findIndex(int * array,int first,int last,int maxmin){

    int ind;
    int answer = first;
    for(ind = answer + 1;ind <= last;++ind){

        if(((maxmin == 1) && (array[answer] < array[ind])) || ((maxmin == 0) && (array[answer] > array[ind]))){

            answer = ind;
        }
    }
    return answer;
}

int findMaxIndex(int * arr,int first,int last){

    return findIndex(arr,first,last,1);
}

int findMinIndex(int * arr,int first,int last){

    return findIndex(arr,first,last,0);
}


int isStackSortable(int * array,int first,int last)
// 检查该范围内的数组是否可排序
// 当该范围的数组可排序返回1
// 当该范围的数组不可排序返回0
{
    // 只有一个元素 肯定是可排序的
    if(first >= last){
        return 1;
    }
    int maxIndex = findMaxIndex(array,first,last);
    //情况分类
    //1. A与B均为空
    //2. 数组仅有一个元素 则可栈排序

    if(0 == maxIndex){

        return isStackSortable(array,first+1,last);
    }
    else if(last == maxIndex){

        return isStackSortable(array,first,last-1);
    }
    int leftMaxAIndex = findMaxIndex(array,first,maxIndex-1);
    int rightMinBIndex = findMinIndex(array,maxIndex+1,last);

    if(array[leftMaxAIndex] > array[rightMinBIndex]){

        return 0;
    }
    int sortA = isStackSortable(array,first,maxIndex-1);
    int sortB = isStackSortable(array,maxIndex+1,last);

    return (sortA && sortB);
}

//
void printfArray(int * array,int length){

    if(isStackSortable(array,0,length-1) == 0){

        printf("不能使用栈排序法进行排序.\n");
        return;
    }
    for(int index = 0;index < length;++index){

        printf("%d. ",array[index]);
    }
    printf("\n");
}

// 对数组的元素进行全排列
void permuteHelp(int * array,int ind,int num){

    if(ind == num){

        printfArray(array,num);
        return;
    }
    int loc;
    for(loc = ind;loc < num;++loc){

        swap(&array[loc],&array[ind]);
        permuteHelp(array,ind+1,num);
        swap(&array[loc],&array[ind]);
    }
}

void permute(int * array,int length){

    permuteHelp(array,0,length);    
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int
main(int argc,char * argv){

    // return EXIT_SUCCESS;
    int number = 4;
    int * checkArrays = arrGen(number,NULL);

    printArray(checkArrays,number);
    permute(checkArrays,number);

    free(checkArrays);
    return 0;
}